0022. 向上取整的不同写法

• 1. 🎯 本节内容
• 2. 🫧 评价
• 3. 🤔 为什么在离散世界中我们需要“向上取整”？
• 4. 🤔 “向上取整”的数学表达是？
• 5. 🤔 既然有 Math.ceil，为什么算法界还执着于 (n + t - 1) / t？
  • 5.1. 跨语言通用性
  • 5.2. 纯整数运算优势
  • 5.3. 面试考点
• 6. 🤔 公式 (n + t - 1) / t 是如何通过数学推导严格证明的？
  • 6.1. 情况一：整除时 r = 0
  • 6.2. 情况二：有余数时（1 ≤ r < t）
• 7. 🤔 为什么偏移量选择的是 + (t - 1) 而不是 + 1 或 + 其他数字？
• 8. 🤔 这个技巧还能推广到负数或非整数场景吗？
  • 8.1. 负数场景的问题
  • 8.2. 非整数场景
• 9. 🤔 实战：如何在分页业务中灵活应用这一公式？
• 10. 🤔 实战：在代码审查（Code Review）中，我们该如何选择最适合的写法？

1. 🎯 本节内容

• 向上取整的不同写法

2. 🫧 评价

在 JS 中，如果我们要对运算 n / t 的结果进行向上取整，首先可能会想到使用 Math.ceil(n / t)。但是，这种写法有一定的局限性，并不具备跨语言的通用性，更为通用的写法是 Math.floor((n + t - 1) / t)。

在刷算法题的时候接触到了 Math.floor((n + t - 1) / t) 这种整数除法向上取整的方式，开始不太理解，因此写这篇笔记来梳理下它的数学推导过程。

3. 🤔 为什么在离散世界中我们需要“向上取整”？

在现实世界的许多场景中，我们无法处理“部分”单位，必须使用完整的整数单位。这就是向上取整存在的根本原因。以下是两个经典场景：

分页计算：

• 假设数据库中有 100 条数据，每页显示 25 条，那么需要 4 页。
• 但如果数据是 101 条，每页 25 条，则需要 5 页。
• 因为第 5 页虽然只有 1 条数据，但仍然需要占用一个完整的页面。

装箱问题：

• 有 10 个物品，每个箱子最多装 3 个，那么需要 4 个箱子。
• 前 3 个箱子各装 3 个，第 4 个箱子装 1 个。
• 即使最后一个箱子没装满，也需要一个完整的箱子。

4. 🤔 “向上取整”的数学表达是？

这些场景都可以抽象为同一个数学问题：给定总数 n 和每份容量 t，求至少需要多少份。用数学符号表示就是：

$$\lceil \frac{n}{t}\rceil$$

其中向上取整符号表示无论小数部分多小，都要进到下一个整数。

如果在 markdown 中书写的话，对应的 LaTex 的语法如下：

$$
\lceil \frac{n}{t} \rceil
$$

5. 🤔 既然有 Math.ceil，为什么算法界还执着于 (n + t - 1) / t？

Math.ceil 是 JavaScript 中用于对数字进行向上取整的内置 API，并且看起来更直观（一眼就知道这里是在做向上取整的操作），但你可能会在不少题解中看到类似这样的写法 Math.floor((n + t - 1) / t) 来实现向上取整的效果，虽然它不那么直观，但在算法竞赛和跨语言开发中，Math.floor((n + t - 1) / t) 才是标准写法，这背后有三个核心原因。

5.1. 跨语言通用性

不同编程语言对除法的处理方式不同。在 C++、Java、Go 等语言中，整数除法会自动向下取整，没有内置的向上取整函数。

使用 Math.ceil 写法：

• 在 C++ 中需要写成 (int)ceil((double)n / t)
• 涉及整数到浮点数再到整数的类型转换
• 代码无法直接移植

使用 (n + t - 1) / t 写法：

• 在 C++、Java、JavaScript、Python 中写法完全一致
• 无需任何类型转换
• 一行代码可以在所有语言中直接运行

5.2. 纯整数运算优势

Math.ceil 依赖浮点运算单元，而 (n + t - 1) / t 完全在整数域内完成。

在以下场景中，纯整数运算至关重要：

• 嵌入式系统可能没有浮点运算单元
• 内核开发中禁用浮点运算
• 高性能计算中避免浮点开销
• 大整数运算中浮点数会丢失精度

5.3. 面试考点

在技术面试中，写出 (n + t - 1) / t 会被认为：

• 理解离散数学原理
• 有跨语言开发经验
• 基础扎实，不依赖库函数

而只写 Math.ceil 可能被认为只是调用了 API，没有深入理解背后的数学逻辑。

6. 🤔 公式 (n + t - 1) / t 是如何通过数学推导严格证明的？

我们要证明的核心等式是：

$$\lceil \frac{n}{t}\rceil =\lfloor \frac{n+t-1}{t}\rfloor$$

其中 n 和 t 都是正整数。

根据带余除法，任何整数 n 除以正整数 t 都可以唯一表示为：

$$n=q\times t+r$$

其中：

• q 是商，等于 Math.floor(n / t)
• r 是余数，满足 0 ≤ r < t

6.1. 情况一：整除时 r = 0

当 n 能被 t 整除时，余数 r 等于 0，此时 n = q × t。

左边计算：

$$\lceil \frac{n}{t}\rceil =\lceil \frac{q\times t}{t}\rceil =\lceil q\rceil =q$$

右边计算：

$$\lfloor \frac{n+t-1}{t}\rfloor =\lfloor \frac{q\times t+t-1}{t}\rfloor =\lfloor q+\frac{t-1}{t}\rfloor$$

因为 t ≥ 1，所以 0 ≤ (t - 1) / t < 1，向下取整后小数部分消失：

$$=q+0=q$$

左右两边相等，整除情况得证。

6.2. 情况二：有余数时（1 ≤ r < t）

当 n 不能被 t 整除时，余数 r 至少为 1，此时 n = q × t + r。

左边计算：

$$\lceil \frac{n}{t}\rceil =\lceil q+\frac{r}{t}\rceil$$

因为 0 < r / t < 1，所以 q < q + r / t < q + 1，向上取整后：

$$=q+1$$

右边计算：

$$\lfloor \frac{n+t-1}{t}\rfloor =\lfloor \frac{q\times t+r+t-1}{t}\rfloor =\lfloor q+1+\frac{r-1}{t}\rfloor$$

因为 1 ≤ r < t，所以 0 ≤ r - 1 < t - 1 < t，即 0 ≤ (r - 1) / t < 1：

$$=q+1+0=q+1$$

左右两边相等，有余数情况得证。

7. 🤔 为什么偏移量选择的是 + (t - 1) 而不是 + 1 或 + 其他数字？

这是理解该公式最关键的问题。偏移量的选择必须满足两个边界条件：

1. 整除时不误判
2. 有余数时必进位

我们可以对上述两个边界条件做以下简单分析：

• Q：整除时要做到不误判，偏移量的取值范围是多少？
• A：整除时，余数 r = 0，为了确保无进位，偏移量最小是 1，最大是 t - 1，因此范围是 [1, t - 1]。（区间 1）
• Q：如何确保有余数 r 时，必进位？
• A：只需要确保最小的余数 1 能够进位即可，t - 1 是满足条件的最小偏移量，此时最大的偏移量是 2t - r - 1，因此范围是 [t - 1, 2t - r - 1]。（区间 2）

区间 1 和 区间 2 的交集正好就是 t - 1，因此 t - 1 才是唯一正确的偏移量。

8. 🤔 这个技巧还能推广到负数或非整数场景吗？

公式 (n + t - 1) / t 的推导基于一个关键假设：n 和 t 都是正整数，仅适用于正整数场景。当这个假设不成立时，公式可能失效，此时应回归使用语言内置的取整函数，或添加额外的条件判断。

8.1. 负数场景的问题

当 n 为负数时，向上取整的行为与正数不同。

例如，设 t = 5：

• n = -5（整除）：期望向上取整为 -1
  • 公式计算：(-5 + 4) / 5 = -0.2，向下取整得 -1，正确
• n = -6（余数）：期望向上取整为 -1（因为 -6/5 = -1.2，向上取整是 -1）
  • 公式计算：(-6 + 4) / 5 = -0.4，向下取整得 -1，正确
• n = -10（整除）：期望向上取整为 -2
  • 公式计算：(-10 + 4) / 5 = -1.2，向下取整得 -2，正确
• n = -11（余数）：期望向上取整为 -2（因为 -11/5 = -2.2，向上取整是 -2）
  • 公式计算：(-11 + 4) / 5 = -1.4，向下取整得 -2，正确

看起来似乎可行？但问题在于不同语言对负数除法的定义不同：

• JavaScript：-11 / 5 = -2.2，Math.floor(-2.2) = -3
• C++：-11 / 5 = -2（向零取整）
• Python：-11 // 5 = -3（向下取整）

这导致公式在不同语言中对负数的处理结果不一致。

如果需要处理负数，建议使用条件判断：

function ceilDiv(n, t) {
  if (n >= 0) {
    return Math.floor((n + t - 1) / t)
  } else {
    return Math.floor(n / t) // 负数时行为不同
  }
}

或者直接使用 Math.ceil(n / t)，让语言处理负数语义。

8.2. 非整数场景

当 t 不是整数时，公式完全失效。因为 t - 1 的意义是基于整数除法的余数概念，非整数没有余数的定义。

9. 🤔 实战：如何在分页业务中灵活应用这一公式？

// 问题：已知总数据量 total 和每页大小 pageSize，求总页数。

// 传统写法：
const totalPages = Math.ceil(total / pageSize)

// 整数公式写法：
const totalPages = Math.floor((total + pageSize - 1) / pageSize)

// 完整示例：
function calculatePages(total, pageSize) {
  if (total === 0) return 0
  return Math.floor((total + pageSize - 1) / pageSize)
}

// 测试：
calculatePages(100, 25) // 4
calculatePages(101, 25) // 5
calculatePages(0, 25) // 0（需要特殊处理）

10. 🤔 实战：在代码审查（Code Review）中，我们该如何选择最适合的写法？

在团队协作中，代码的可读性和一致性往往比微小的性能差异更重要。以下是代码审查时的建议：

• 可读性优先：在业务代码中，Math.ceil 更直观
• 一致性重要：同一项目内保持写法统一
• 注释补充：使用整数公式时添加注释说明
• 工具函数：抽取为公共函数，避免重复代码
• 测试覆盖：确保整除和有余数的边界情况都有测试

最好的代码不是最聪明的代码，而是最容易被团队成员理解和维护的代码。

• 如果项目是你个人独立负责，那随意选择，做好封装，保持统一即可
• 如果是多人协作的项目，并且团队有明确的开发规范的话，按照规范走即可